package hot100.logos11To20;

/**
 * @author logos
 * date 2025/7/10 11:42
 * @version v1.0
 * @Package hot100
 */
public class logos11 {


    /**
     * 11. 滑动窗口最大值
     * https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            int[] deque = new int[n];
            int l = 0, r = 0;
            for (int i = 0; i < k - 1; i++) {
                while (l < r && nums[deque[r - 1]] <= nums[i]) {
                    r--;
                }
                deque[r++] = i;
            }
            int m = n - k + 1;
            int[] ans = new int[m];
            for (int left = 0, right = k - 1; right < n; left++, right++) {
                while (l < r && nums[deque[r - 1]] <= nums[right]) {
                    r--;
                }
                deque[r++] = right;
                ans[left] = nums[deque[l]];
                if (deque[l] == left) {
                    l++;
                }
            }
            return ans;
        }
    }
}
